package top.whk0710.algorithms.sort;

import java.util.PriorityQueue;
import java.util.Stack;

public class QuickSort {

    public static void main(String[] args){
        final int[] arr = createRondom(70000);
        long start = System.currentTimeMillis();
        quickSort(arr,0,69999);
        System.out.println(System.currentTimeMillis() - start);

        start = System.currentTimeMillis();
        quickSort2(arr,0,69999);
        System.out.println(System.currentTimeMillis() - start);

    }

    public static int[] createRondom(int length){
        int[] arr = new int[length];
        for(int i=0;i<length;i++){
            arr[i] = (int) Math.random()*length;
        }

        return arr;
    }

    /**
     * 分治法
     * */
    public static void quickSort(int[] arr, int l, int h){
        if(l >= h) return;
        //第一次，选中一个key值，将比其小的数放在左边，比其大的放在右边
        int q = partition(arr, l, h);
        //然后递归
        quickSort(arr,l,q-1);
        quickSort(arr,q+1,h);
    }

    public static void quickSort2(int[] arr, int l, int h){
        if(l >= h) return;
        //第一次，选中一个key值，将比其小的数放在左边，比其大的放在右边
        int q = partition2(arr, l, h);
        //然后递归
        quickSort(arr,l,q-1);
        quickSort(arr,q+1,h);
    }

    private static int partition(int[] arr, int p, int r){
        //swap(arr, p, r);
        int key = arr[r];
        int i = p - 1;
        for(int j = p;j < r;j++){
            if(arr[j] <= key){
                i++;
                //i=j不用交换
                if(i!=j){
                    //swap
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
        //swap
        int tmp = arr[r];
        arr[r] = arr[i+1];
        arr[i+1] = tmp;
        i++;

        return i;
    }


    public static int partition2(int[] array,int start,int end){
        //swap(array, start, end);
        int flag = array[start+(int)Math.random()*(end-start)];

        while(start<end){
            while(start<end && array[end]>=flag){
                end--;
            }
            array[start] = array[end];
            while(start<end && array[start]<=flag){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = flag;
        return start;
    }


    public static void swap(int[] array,int num1,int num2){
        int temp =array[num1];
        array[num1] =array[num2];
        array[num2] =temp;
    }

    public static void print(int[] arr){
        for(int i : arr){
            System.out.print(i + " ");
        }
        System.out.println();
    }
}
